package org.example;

import java.util.HashMap;
import java.util.Map;

public class Test4 {
    /**
     * 通过哈希表来记录每个节点的下标值，然后通过下标的关系来链接链表
     * @param head
     */
    public void reorderList(ListNode head) {
        Map<Integer,ListNode> map = new HashMap<>();
        ListNode cur = head;
        int index = 0;
        while (cur != null) {
            map.put(index++,cur);
            cur = cur.next;
        }
        cur = head;
        for (int i = 0; i < index/2; i++) {
            ListNode node = map.get(index-1-i);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        cur.next = null;
    }

    /**
     * 通过观察可以发现，最中间的节点是重排链表之后的最后一个节点，所以我们可以用过快慢指针找到最中间的节点
     * 然后将最中间节点以及之后的节点进行逆序，然后将前半部分的链表和后半部分的链表依次连接
     * 这里需要注意将前半部分的链表的尾节点的next节点置为null，防止出现环
     * @param head
     */
    public void reorderList1(ListNode head) {
        if (head == null || head.next == null) return;
        //通过快慢指针找到链表的中间节点，然后将中间节点之后的链表进行翻转，然后将前半部分的链表和
        //后半部分的链表依次连接
        ListNode slow = head, fast = head, tmp = null;
        while (fast != null && fast.next != null) {
            tmp = slow;
            slow = slow.next;
            fast = fast.next;
            if (fast.next == null) break;
            else fast = fast.next;
        }
        //将前半部分的链表的尾节点的next节点置为null，防止产生环
        tmp.next = null;
        //翻转slow指针之后的链表
        ListNode prev = null;
        while (slow != null) {
            ListNode nextNode = slow.next;
            slow.next = prev;
            prev = slow;
            slow = nextNode;
        }
        ListNode cur = head;
        while (cur != null) {
            ListNode prevNext = cur.next;
            ListNode nextNext = prev.next;
            //防止后半部分的链表长度比前半部分的链表长度长1，导致最后一个节点丢失
            if (cur.next != null) {
                prev.next = cur.next;
            }
            cur.next = prev;
            cur = prevNext;
            prev = nextNext;
        }
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        a.next = b;
        b.next = c;
        c.next = d;
        Test4 test4 = new Test4();
        test4.reorderList(a);
        System.out.println(666);
    }
}
